#ifndef AVLIMP_CPP
#define AVLIMP_CPP
#include "AVLImp.h"
//Publicos
//typedef nodoAVLPtr nodoAVLPtr;
template <class T>
AVLImp<T>::AVLImp(){
	Raiz = NULL;
	this->lista=new ListaImp<T>();
}

template <class T>
void AVLImp<T>::agregar(const T &e){
	insertar(e,Raiz);
}

template <class T>
AVLImp<T>::~AVLImp(){
	vaciar();
}

template <class T>
void AVLImp<T>::vaciar(){
	this->lista->Vaciar();
	borrarArbol();
	Raiz = NULL;
}

template <class T>
void AVLImp<T>::borrarArbol(){
	borrarArbolAux(Raiz);
}

template <class T>
void AVLImp<T>::borrarNodo(const T e){
	borrarElemento(e,Raiz);
}

template <class T>
T AVLImp<T>::datoRaiz(){
	return Raiz->dato;
}

template <class T>
const bool AVLImp<T>::esVacio(){
	return Raiz == NULL;
}

template <class T>
const bool AVLImp<T>::esMiembro(const T &e){
	bool esta = pertenece(e, Raiz);
	return esta;
}

template <class T>
const void AVLImp<T>::imprimir(){
	this->lista->Vaciar();
	imprimirAux(Raiz);
}

//Privados

template <class T>
void AVLImp<T>::insertar(const T &e,nodoAVLPtr &n){

	nodoAVLPtr p1;
	nodoAVLPtr p2;
	
	if(n==NULL){
		n = new NodoAVL<T>();
		n->dato=e;
		n->balance=0;
		n->izq=NULL;
		n->der=NULL;
		this->vario_h=true;
	}else{
		if(n->dato>e){
			insertar(e,n->izq);
			if(vario_h){ /* crecio altura de subarbol izquierdo */
				/* Balanceo arbol izquierdo */
				switch(n->balance){
					case 1:
						n->balance=0;
						this->vario_h=false;
						break;
					case 0:
						n->balance=-1;
						break;
					case -1:
						p1=n->izq;
						if(p1->balance==-1){
							//rotacion simple
							n->izq=p1->der;
							p1->der=n;
							n->balance=0;
							n=p1;
						}else{
							//rotacion doble
							p2=p1->der;
							p1->der=p2->izq;
							p2->izq=p1;
							n->izq=p2->der;
							p2->der=n;
							n->balance=p2->balance==-1?1:0;
							p1->balance=p2->balance==1?-1:0;
							n=p2;
						}
						this->vario_h=false;
						n->balance=0;
						break;
				}
			}
		}else if(n->dato<e){
				insertar(e,n->der);
				if(this->vario_h){
					/* crecio la altura subarbol derecho */
					/* Balanceo arbol derecho */
					switch(n->balance){
						case -1:
							n->balance=0;
							this->vario_h=false;
							break;
						case 0:
							n->balance=1;
							break;
						case 1:
							p1=n->der;
							if(p1->balance==1){
								//rotacion simple
								n->der=p1->izq;
								p1->izq=n; 
								n->balance=0;
								n=p1;
							}else{
								//rotacion doble
								p2=p1->izq;
								p1->izq=p2->der;
								p2->der=p1;
								n->der=p2->izq;
								p2->izq=n;
								n->balance=(p2->balance==1?-1:0);
								p1->balance=p2->balance==-1?1:0;
								n=p2;
							}
							this->vario_h=false;
							n->balance=0;
					}
				}
		}else{
			n->dato=e;
			vario_h=false;
		}
	}
}

template <class T>
void AVLImp<T>::borrarArbolAux(nodoAVLPtr &n){
	if(n!= NULL){
		borrarArbolAux(n->der);
		borrarArbolAux(n->izq);
		n = NULL;
	}
}

template <class T>
const bool AVLImp<T> :: pertenece(const T &e, nodoAVLPtr &n){
	bool esta = false;
	if (n != NULL){
		if (n -> dato == e){
			esta = true;
		} else{
			esta = pertenece(e, n -> izq)||pertenece(e, n -> der);
		}
	}
	return esta;
}

template <class T>
void AVLImp<T>::borrarElemento(T e, nodoAVLPtr &n){
	if (n!= NULL) {
		if (n->dato < e) {
			//Voy por derecha
			borrarElemento( e,n->der);
			if (vario_h) BalanceoD(n);
		}
		else if (n->dato > e) {
			//Voy por izquierda
			borrarElemento( e,n->izq);
			if (vario_h) BalanceoI(n);
		}
		else {

			if (n->der != NULL && n->izq != NULL) {// *NO* es una hoja
				nodoAVLPtr navegador = n->izq;
				//me quedo con el hijo izquierdo y busco el mayor hijo derecho
				nodoAVLPtr pred = maximo(navegador);
				n->dato = pred->dato;
				//a n le pongo el dato del mayor dato del hijo izquierdo y llamo a borrar con el hijo izquierdo y el dato del maximo	
				borrarElemento(pred->dato,n->izq);
				//Balanceo el arbol
				if (vario_h) BalanceoI(n);
			}
			else {
				nodoAVLPtr temp = n;
				if (n->der == NULL)
					n = n->der;
				else
					n = n->der;
				temp=NULL;
				//delete temp;
				vario_h = true;
			}	
		}
	}
}

template <class T>
void AVLImp<T>::BalanceoD(Puntero<NodoAVL<T>> &n){
	nodoAVLPtr p1;
	nodoAVLPtr p2;

	switch(n->balance){
		case 1:
						n->balance=0;
						this->vario_h=false;
						break;
					case 0:
						n->balance=-1;
						vario_h = false;
						break;
					case -1:
						p1=n->izq;
						if(p1->balance==-1){
							//rotacion simple
							n->izq=p1->der;
							p1->der=n;
							n->balance=0;
							n=p1;
						}else{
							//rotacion doble
							p2=p1->der;
							p1->der=p2->izq;
							p2->izq=p1;
							n->izq=p2->der;
							p2->der=n;
							n->balance=p2->balance==-1?1:0;
							p1->balance=p2->balance==1?-1:0;
							n=p2;
							//ojo
							//n->balance=-1;
							
						}	
						this->vario_h=false;
						n->balance=0;
						break;
		}
			
	
}
//fin balanceoI

template <class T>
void AVLImp<T>::BalanceoI(nodoAVLPtr &n){
	nodoAVLPtr p1;
	nodoAVLPtr p2;
	
	switch(n->balance){
					case 1:
						n->balance=0;
						this->vario_h=false;
						break;
					case 0:
						n->balance=-1;
						break;
					case -1:
						p1=n->izq;
						if(p1->balance==-1){
							//rotacion simple
							n->izq=p1->der;
							p1->der=n;
							n->balance=0;
							n=p1;
						}else{
							//rotacion doble
							p2=p1->der;
							p1->der=p2->izq;
							p2->izq=p1;
							n->izq=p2->der;
							p2->der=n;
							n->balance=p2->balance==-1?1:0;
							p1->balance=p2->balance==1?-1:0;
							n=p2;
						}
						this->vario_h=false;
						n->balance=0;
						break;
						}
			}

template <class T>
void AVLImp<T>::rotacionSimpleD(nodoAVLPtr &n){
	nodoAVLPtr aux = n -> izq;
	n -> izq = aux -> der;
	aux -> der = n;
	n = aux;
}


template <class T>
void AVLImp<T>::rotacionSimpleI(nodoAVLPtr &n){
	nodoAVLPtr aux = n -> der;
	n -> der = aux -> izq;
	aux -> izq = n;
	n = aux; 
}


template <class T>
void AVLImp<T>::rotacionDobleD(nodoAVLPtr &n){
	nodoAVLPtr n2 = n -> izq;
	nodoAVLPtr n3 = n2 -> der;
	n2 -> der = n3 -> izq;
	n -> izq = n3 -> der;
	n3 -> izq = n2;
	n3 -> der = n;
	n = n3;
}


template <class T>
void AVLImp<T>::rotacionDobleI(nodoAVLPtr &n){
	nodoAVLPtr n2 = n -> der;
	nodoAVLPtr n3 = n2 -> izq;
	n2 -> izq = n3 -> der;
	n -> der = n3 -> izq;
	n3 -> der = n2;
	n3 -> izq = n;
	n = n3;
}


template <class T>
const void AVLImp<T>::imprimirAux(nodoAVLPtr n){
	if (n != NULL){
		imprimirAux(n->izq);
		this->lista->Agregar(n->dato);
		cout<<n->dato<<endl;
		imprimirAux(n->der);
	
	}
}

template <class T>
int AVLImp<T>::altura(nodoAVLPtr n){
	return n != NULL ? n-> altura : -1;
}


template <class T>
int AVLImp<T>::max(int a, int b){
	return a > b ? a : b;
}

template <class T>
Puntero<NodoAVL<T>> AVLImp<T>::maximo(Puntero<NodoAVL<T>> n)
{
	if(n!=NULL){
		if(n->der==NULL){
			return n;
		}else{
			return maximo(n->der);
		}
	}
	else return NULL;

}
template <class T>
Puntero<Iterador<T>> AVLImp<T>::ObtenerIterador()const
{
		return  new IteradorListaImp<T>(*this->lista);

}

template <class T>
int AVLImp<T>::Largo()
{
	//cambiarlo
	return 0;
}
template <class T>
const void AVLImp<T>::CrearIterador()
{
	this->lista->Vaciar();
	iteradorAux(Raiz);
}
template <class T>
const void AVLImp<T>::iteradorAux(nodoAVLPtr n){
	if (n != NULL){
		iteradorAux(n->izq);
		this->lista->AgregarFinal(n->dato);
		iteradorAux(n->der);
	}
}



#endif